The PACE protocol was developed by the German Budesamt für Sicherheit in Informationstechnik (BSI), originally for application within electronic passports. The PACE protocol will be used as an example of an elliptic curve key exchange protocol in the embodiments described below. The PACE protocol establishes a high entropy shared key between participants by first encrypting a random nonce under a password-derived key and then performing a mapping from this nonce to a random basepoint for a Diffie-Hellman key exchange (DHKF). Because this mapped basepoint is not known to the attacker, the protocol is secure against active man-in-the-middle adversaries and no distinguisher of a correct password guess is presented to an attacker, providing resistance against dictionary attacks on the password space.
FIG. 1 illustrates the PACE protocol in its most general form using elliptic curve cryptography (ECC). The nonce s 105 is randomly selected. A shared password 110 may then be hashed using a hash function 115 to generate a key K 120. The nonce s 105 may be encrypted 125 using the key K 120. The encrypted nonce s is then decrypted 130 using the same key K 120 derived from the shared password 110 resulting in the nonce s in the clear. The nonce s 105 is mapped 135 to a point Gmap 140 on an agreed upon elliptic curve. As a result Gmap, should be unknowable to an attacker. Gmap may then be used as a basepoint for an elliptic curve Diffie-Hellman key exchange (EC-DHKF).
The EC-DHKF is also shown. A first party selects a random value rP which is multiplied 150 with the base point Gmap using an elliptic curve point multiplication to produce RPICC 155. The value RPICC 155 is then shared with a second party. The second party selects a random value rT which is multiplied 160 with the base point Gmap using an elliptic curve point multiplication to produce RTERM 165. The value RTERM 165 is then shared with the first party. The first party then multiplies 170 RTERM 165 by rP using an elliptic curve point multiplication to obtain a value that is input to a key definition function (KDF) 180 to produce a shared encryption key. The second party then multiplies 175 RPICC 155 by rT using an elliptic curve point multiplication to obtain a value that is input to a key definition function KDF 185 to produce a shared encryption key which is the same as the key produced by the first party using KDF 180.
This EC-DHKF is secure against man-in-the-middle attacks while the protocol is executing because it is conducted with an unknown basepoint, and nothing is revealed which gives the attacker a better-than-guessing advantage in learning the password.
Various mapping functions may be used to create Gmap. The mapping function seeks to produce a random generator in the elliptic curve group, either by directly hashing onto the curve (integrated mapping) or, as in the case of the so-called generic mapping, using an initial Diffie-Hellman exchange and then computing sG+H, where H is the point created by the initial EC-DHKF.
The generic mapping can also be augmented by a so-called “CAM mapping”. This is not really a different mapping function but rather an extra protocol step in which a device performs a verifiable private key operation with a single modular multiplication (using the inverse of the device private key) re-using a random point from the generic mapping exchange; this CAM mapping process is not described herein, but it can be applied.